/*
    libnbds
    Non-blocking Data Structures Library

    Copyright (C) 2011 Paweł Dziepak

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef NBDS_MAP_H
#define NBDS_MAP_H

namespace nbds {
	class map_base {
	private:
		struct elem {
			void *key;
			void *value;

			elem *lesser;
			elem *greater;
		};

		elem *root;

		void cpy_elem_r(elem**, elem*);
		void del_elem_r(elem*);
		bool nul_elem_r(elem*);

		bool try_add(elem*, bool);

	protected:
		virtual bool cmp_eq(const void *a, const void *b) const = 0;
		virtual bool cmp_g(const void *a, const void *b) const = 0;
		virtual bool cmp_l(const void *a, const void *b) const = 0;

		void *(*cpy_kp)(void *obj);
		void *(*cpy_vp)(void *obj);

		void (*del_kp)(void *obj);
		void (*del_vp)(void *obj);
	public:
		map_base();
		map_base(const map_base &, void *(*)(void*), void *(*)(void*));
		~map_base();

		void *get_(const void*) const;
		void set_(void*, void*);

		void add_(void*, void*);
		void *remove_(const void*);

		bool is_empty_();
	};

	template<typename T, typename U>
	class map : public map_base {
	private:
		virtual bool cmp_eq(const void *a, const void *b) const {
			return *reinterpret_cast<const T*>(a) == *reinterpret_cast<const T*>(b);
		}

		virtual bool cmp_g(const void *a, const void *b) const {
			return *reinterpret_cast<const T*>(a) > *reinterpret_cast<const T*>(b);
		}

		virtual bool cmp_l(const void *a, const void *b) const {
			return *reinterpret_cast<const T*>(a) < *reinterpret_cast<const T*>(b);
		}

		static void del_k(void *obj) {
			delete reinterpret_cast<T*>(obj);
		}

		static void del_v(void *obj) {
			delete reinterpret_cast<U*>(obj);
		}

		static void *cpy_k(void *obj) {
			return new T(*reinterpret_cast<T*>(obj));
		}

		static void *cpy_v(void *obj) {
			return new U(*reinterpret_cast<U*>(obj));
		}

	public:
		map() : map_base() { }
		map(const map<T, U> &obj) : map_base(obj, cpy_k, cpy_v) { }
		~map() {
			del_vp = del_v;
			del_kp = del_k;
		}

		U get(const T &key) const {
			U *ptr = reinterpret_cast<U*>(get_(&key));
			if (ptr)
				return *ptr;
			else
				return U();
		}

		void set(const T &key, const U &value) {
			set_(new T(key), new U(value));
		}

		void add(const T &key, const U &value) {
			add_(new T(key), new U(value));
		}

		U remove(const T &key) {
			U *ptr = reinterpret_cast<U*>(remove_(&key));
			if (ptr)
				return *ptr;
			else
				return U();
		}

		bool is_empty() {
			return is_empty_();
		}
	};
}

#endif
